Feature #4: Query Peak Users

Description#

The cellular operator serves a rectangular region, represented by a 2D grid with one base station in each cell. Each base station is limited in the number of simultaneous users. During busy hours, some users get poor or no service. The company leadership wants to fix this problem by deploying multiple base stations, wherever necessary. Since this is a capital-intensive plan, we want to systematically deploy new base stations only where they are bound to help the most.

The operator has gathered the peak number of users connected to each base station. The executives want to query the obtained data and calculate the peak number of users that are connected to the base stations in a rectangular subset of the covered area. The executives may need to query the data multiple times. Therefore, we need to figure out an efficient way to execute the queries and return their results.

Note: The area to be queried is identified by the top-left and bottom-right cell coordinates.

The following illustration will help clarify to this problem:

Solution#

A beginner’s way of solving this problem is to use nested loops to iterate over the rectangular region, represented by the top-left $(row1, col1)$ and bottom-right $(row2, col2)$ coordinates, and sum up all the elements in that region.

Since the executives may want to query the data multiple times, it would make sense for us to perform some pre-processing.

Caching#

We could use extra space for speeding up the algorithm by pre-calculating all the possible rectangular regions and storing them in a hash map. This way, all the queries will take constant time. However, the space complexity will blow up, because we have to store all the possible regions.

Let’s see how we can build on this intuition of caching the results.

Caching rows#

Imagine pre-computing the cumulative sum of the elements for each row in the grid. We can derive a formula that will calculate the cumulative sum for each individual row $i$, ranging from $0 ...rows - 1$ (inclusive):

$$cache[i][j]=\begin{cases}\sum_{k=0}^{j-1} users[i][k]& j \gt 0 \\ 0 & j = 0\end{cases}$$

Here, $j$ ranges from $0$ to the total number of columns, $(cols)$ in the input grid users. We will calculate the prefix sum of all the cells in a row and store them at the appropriate cell in a 2D grid cache of order $rows \times cols + 1$. We can simplify the notation given above and make use of the sum calculated in the last iteration:

$$cache[i][j + 1]=\begin{cases} users[i][j]+cache[i][j] & j \gt 0 \\ 0 & j = 0\end{cases}$$

Note: We can observe from our formulation that the cache grid will have an additional column, which will contain only zeros.

Let’s review the following illustration to understand this formulation better:

Once we have cached the prefix sums, we can accumulate the sum in the region row by row. The subset region is identified by the starting and ending cell coordinates, $(row1, col1)$ and $(row2, col2)$. We can derive a formula for calculating the sum as well:

$$sum[row1...row2][col1...col2] = \sum_{i=row1}^{row2} cache[i][col2 + 1] - cache[i][col1]$$

As the $cache[i][col2 + 1]$ contains the prefix sum of the elements up to that column, that is, $col2 + 1$ (exclusive), we will need to subtract the cells that are not part of the subset region, which is, $cache[i][col1]$.

Let’s review an example of this:

Smart caching#

Similar to our approach from above, where we pre-calculated the prefix sum for a row, we can pre-compute a cumulative region sum with respect to the origin at $(0, 0)$.

For a cell that is represented by its coordinates $(row, col)$, we will compute the cumulative region sum from the origin at $(0, 0)$ and cache that using the following formula:

$$cache[row][col] = \sum_{i = 0}^{i = row}\sum_{j = 0}^{j = col}users[i][j]$$

We can use the formulation given above for pre-calculating the cumulative sum for all the regions. However, we can do this more efficiently by making use of the cumulative sum of the regions that has already been calculated:

$$cache[i + 1][j + 1] = cache[i + 1][j] + cache[i][j + 1] + users[i][j] - cache[i][j]$$

Here $i$ and $j$ range from $0$ to the $number\ of\ rows\ and\ columns$, respectively, and the output cache is of order $rows + 1 \times cols + 1$

Note: For the sake of simplicity and making the calculations easier to understand, we will set all the elements in the zeroth row and the column of the cache to zero.

Let’s review an illustration that represents the cumulative sum of the region:

The cumulative sum of the region is calculated with respect to the origin. Therefore, we have to ensure that the sub-regions that are not part of the queried region are subtracted. We can extract the sum for the region, which is identified by the coordinates $(row1, col1)$ and $(row2, col2)$, from the cache with the following formula:

$$sum[row1...row2][col1...col2] = cache[row2 + 1][col2 + 1] - cache[row1][col2 + 1] - cache[row2 + 1][col1] + cache[row1][col1]$$

Note: We used the principle of inclusion-exclusion here.

We will add the cumulative sum of the region $cache[row1][col1]$, because this region is covered twice by both $cache[row1][col2 + 1]$ and $cache[row2 + 1][col1]$.

Let’s review an example of this:

Complexity measures#

Here $m$ and $n$ will represent the number of rows and columns, respectively.

Time complexity#

Let’s look at the time complexities for the methods, one by one:

• brute_force: $O(m \times n)$ time per query.
• cache_rows: $O(m)$ time per query, $O(m \times n)$ time pre-computation
  • The pre-computation in the constructor will take $O(m \times n)$ time.
  • The cache_rows query will take $O(m)$ time.
• cache_smart: $O(1)$ time per query, $O(m \times n)$ time pre-computation
  • The pre-computation in the constructor will take $O(m \times n)$ time.
  • Each cache_smart query will take $O(1)$ time.

Space complexity#

Similarly, for the space complexity:

• brute_force: Since the algorithm only uses a constant amount of additional space, the space complexity will be $O(1)$.
• cache_rows: The algorithm will use $O(m \times n)$ space to store the cumulative sum of all the rows.
• cache_smart: The algorithm will use $O(m \times n)$ space to store the cumulative sum of the region.